package leet.ku._107;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class Solution {

	class Record {
		int level;
		TreeNode node;

		Record(int l, TreeNode n) {
			level = l;
			node = n;
		}
	}

	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
		if (root == null)
			return result;
		
		Queue<Record> queue = new LinkedList<Record>();
		queue.add(new Record(0, root));
		
		int lastLevel = 0;
		List<Integer> nowLine = new ArrayList<Integer>();
		while (!queue.isEmpty()) {
			Record record = queue.poll();
			if (record.level > lastLevel) {
				result.addFirst(nowLine);
				nowLine = new ArrayList<Integer>();
				lastLevel = record.level;
			}
			nowLine.add(record.node.val);
			if (record.node.left != null)
				queue.add(new Record(record.level + 1, record.node.left));
			if (record.node.right != null)
				queue.add(new Record(record.level + 1, record.node.right));
		}
		result.addFirst(nowLine);
		
		return result;
	}
}